http://blog.163.com/lfw2565295@126/blog/static/12200516201112882117229/
题意﹕给了一字串，长度为。 设为一长度的前缀。 我们把一个长度为的字串说是-回文，若以下条件成立﹕ 
1) 是一个回文； 
2) 的前缀和后缀皆是-回文。 根据定义，任意字串(包括空字串)皆为0-回文。 

现在设若且仅若是一个-回文。 题目要求。 

未进入解之前，首先需要了解一件事。 

引理1 ﹕对于任何长度为的字串，若是回文，是-回文的话，那么的长度为的后缀也是-回文，并且和相同。 

证明1 ：设为字串的逆字串。 假设的长度为的前后缀分别为和。 设，。 那么。 因为，。 因此有和。 若是-回文，则本来。 因此，即也是-回文。 

因此，我们算的时候可以用动态规划﹕ 

那么，答案是求所有前缀回文，并以上述转移方程算出阵列和即可。 
问题是﹕ 如何有效地求所有前缀回文 ？ 

想了几天，实在没有头绪。 如果直接算最长前缀回文的话就很简单的，只需利用失败函数和字串即可。 可是它却不似包含了所有前缀回文的资讯。 因此，放弃了，找到几个日本人写的blog，发现他们用了一个算法，叫 Manacher Algorithm 。 它的目的是求出最长前缀回文的中点，但计算过程则计算了 所有 以某字元可延伸的最长回文长度。 那么此算法则包括找出所有前缀回文，当然，也可以用来找最长前缀回文。 先介绍此算法。 

Manacher算法 
对于长度为的字串，定义为最大整数使得即以第字元为单位的最长可延伸成回文的 半径 。 Manacher给了以下定理﹕ 

定理2 :对于，则有 

和 
。 

证明2 :先证明1)。 因为第字元半径为，当中第字串的半径是。 若果不超过的话，表示第字元的最长可延伸回文被第字元的包含了，则用类似 定理1可以得出(即)。 否则的话，假设，那么第字元的最长可延伸回文超越了第字元的。 但基于类似 定理1 (我们可以把定义为任意回文)，第字元可以再延伸，则不是最长的，因此有矛盾。 所以(最不突破界限的半径作为其半径)。 
对于2)，则可以基于1)的去思考。但第字元的半径则却可以突破第字元的半径。 考虑以下字串﹕ 

01abbaccabbac 
   | i | 
   xy 

现在设。 可以看到但。 

那么，利用 定理2 计算所有字元的半径会否很高效？ 首先，留意到对于第字元，任何第位经1)去更新数值的时候，已经不用重覆计算。 唯一的情况则是2)发生，而且枚举的时候， 2)只会发生在1)之后 。 因此，当枚举至的时候2)发生了，则跟据 定理2 所示，立即跳至第位计算其半径。 因为定理说明，因此找出可直接从算起。 因此可知的跳跃是随的增加而加快的。 算法被证明是的。 我没有很小心的去证明，但可以联想的是少的话，虽然增长很慢(每次移很少)但半径都很少，因此每次迭代都很快完；相反很大的话，我们很快就可以以一次送代算出大部分并且大幅前跃，感觉也很快会完成。 

至于编写的时候，留意上述是适用于偶数长度半径，但奇数长度半径又怎样算出来呢？这里 的方法是插入dummy点来计算半径，但每个字元会被多算一次。 这方法亦可看作迭代的时候移动 半步 ，而枚举其半径时也以 半步为单位移动 。 

计算了之后可以简单地找出前缀回文的末点，然后应用最被初的转移方程计算答案。 

下面算法只能处理偶数的情况，
如果串是奇数这么处理
每个字符复制一次，最后长度/2
aabbccbbaa
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <numeric>
#include <set>

using namespace std;
const int maxn = 300005;
char s[maxn];
int len[maxn];//len从0到n-1，保存
int n;
void calLen(){
    len[0] = 0;
    int i = 1, j = 0;
    while(i < n){
        while(i-1-j >= 0 && i+j<n && s[i-1-j] == s[i+j]) j ++;
        len[i] = j;
        for(int k = 1; ;k ++){
            if(len[i-k]+k >= len[i]){
                i += k;
                j = max(j - k, 0);
                break;
            }
            len[i+k] = len[i-k];
        }
    }
//    for(int i = 1; i < n; i ++) printf("i = %d len = %d\n", i, len[i]);
}
vector<int> vec[maxn*2];
int main() {
    int test;
    scanf("%d", &test);
    while(test --){
        scanf("%s", s);
        n = strlen(s);
        calLen();
        for(int i = 1; i < n; i ++) vec[i].clear();
        set<int> ss;
        int ans = 0, tx, ty;
//        printf("%d\n", len[2]);
        for(int i = 1; i < n; i ++){
            int x = len[i];
            if(x){
                set<int>::iterator it = ss.lower_bound(i-x);
                if(it != ss.end()){
                    int v = *it;
                    assert(i-v <= x);
                    assert(len[v] >= (i-v)*2);
                    if(i - v > ans){
                        ans = i - v;
                        tx = v; ty = i;
                    }
                }
            }
            if(x/2 != 0){
                vec[i+x/2].push_back(i);
                ss.insert(i);
            }
            for(int j = 0; j < (int)vec[i].size(); j ++){
                ss.erase(vec[i][j]);
            }
        }
        printf("%d\n", ans*4);
    }
    return 0;
}

